package codingforgreat.lchot150;

public class Lc028 {
    public int strStr(String haystack, String needle) {
        if(haystack.length() < needle.length()){
            return -1;
        }
        char[] s1 = haystack.toCharArray();
        char[] s2 = needle.toCharArray();
        int[] nexts = getNexts(s2);
        int x = 0;
        int y = 0;
        while(x < s1.length && y < s2.length){
            if(s1[x] == s2[y]){
                x++;
                y++;
            }else if(nexts[y] == -1){
                x++;
            }else{
                y = nexts[y];
            }
        }
        return y==s2.length ? x - y : -1;
    }
    public int[] getNexts(char[] str){
        if(str.length == 1){
            return new int[]{-1};
        }
        int[] nexts = new int[str.length];
        nexts[0] = -1;
        nexts[1] = 0;
        int i = 2;
        int cn = 0;
        while(i < str.length){
            if(str[i - 1] == str[cn]){
                nexts[i++] = ++cn;
            }else if(cn > 0){
                cn = nexts[cn];
            }else{
                nexts[i++] = 0;
            }
        }
        return nexts;
    }
}
